package q75_sortColors;

import java.util.Arrays;

public class Solution_2 {
    public static void main(String[] args) {
        Solution_2 s = new Solution_2();
        int[] arr = new int[]{2,1};
        s.sortColors(arr);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 双指针的解法：
     * 在之前的方法中，我们使用了单指针，但是需要遍历两次，有没有双指针的方法，只需要遍历一次？
     * 同样的我们分别使用两个指针在头尾进行遍历，遇到0则放到最前，遇到2则放到最后
     * 但是存在一个问题，当遇到2并交换到最后时，如果此时被交换的是2和2，之后我们就会进行新的交换，意味着这个2被跳过了，导致错误
     * 因此要不断换到i位置不是2为止
     *
     */
    public void sortColors(int[] nums) {
        int n = nums.length;
        int p0 = 0, p2 = n - 1;
        for (int i = 0; i <= p2; ++i) {
            while (i <= p2 && nums[i] == 2) {
                int temp = nums[i];
                nums[i] = nums[p2];
                nums[p2] = temp;
                --p2;
            }
            if (nums[i] == 0) {
                int temp = nums[i];
                nums[i] = nums[p0];
                nums[p0] = temp;
                ++p0;
            }
        }

    }
}
